package BinaryTree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-22
 * Time: 18:22
 */

/**
 * 从前序与中序遍历序列构造二叉树:

 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 *
 *
 *
 * 示例 1:
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 * 示例 2:
 *
 * 输入: preorder = [-1], inorder = [-1]
 * 输出: [-1]
 *
 *
 * 提示:
 *
 * 1 <= preorder.length <= 3000
 */

public class BinaryTreeExercise2 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder, inorder,0,inorder.length-1);
    }


    public int preIndex;
    public TreeNode buildTreeChild(int[] preorder , int[] inorder,int inbegin, int inend) {

        //没有左树或者右树
        if(inbegin > inend) {
            return null;
        }

        //new一个根节点
        TreeNode root = new TreeNode(preorder[preIndex]);

        //在中序遍历中从，前序遍历那里找到，代表所有子树的 根节点
        int rootIndex = findVal(inorder,inbegin,inend, preorder[preIndex]);

        //preIndex，要改为全局变量，左右每次递归是，才不会重置为0
        preIndex++;//rootInde用完才加加；

        //递归每一个创建左右子树
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);

        return root;
    }

    private int findVal(int[] inorder,int inbegin, int inend,int val) {
        for(int i = inbegin; i<=inend; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}
